package com.seu.algorithms.dp;

/**
 * 背包问题
 * 对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
 *
 * @author liangfeihu
 * @since 2019/12/4 14:37
 */
public class Knapsack {
    /**
     * 物品重量
     */
    private int[] weight = {2, 2, 4, 6, 3};
    /**
     * 物品的价值
     */
    private int[] value = {3, 4, 8, 9, 6};
    /**
     * 结果放到 maxW 中
     */
    private int maxW = Integer.MIN_VALUE;
    /**
     * 结果放到 maxV 中
     */
    private int maxV = Integer.MIN_VALUE;
    /**
     * 物品个数
     */
    private int n = 5;
    /**
     * 背包承受的最大重量
     */
    private int w = 9;

    /**
     * 解法一：回溯算法实现
     * 注意：我把输入的变量都定义成了成员变量。
     * 初始调用 f(0, 0)
     */
    public void f(int i, int cw) {
        if (cw == w || i == n) {
            // cw==w 表示装满了，i==n 表示物品都考察完了
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }

        // 选择不装第 i 个物品
        f(i + 1, cw);

        if (cw + weight[i] <= w) {
            // 选择装第 i 个物品
            f(i + 1, cw + weight[i]);
        }
    } // end 回溯算法

    /**
     * 备忘录，默认值 false
     */
    private boolean[][] mem = new boolean[5][10];

    /**
     * 解法二：回溯算法+备忘录模式
     */
    public void f2(int i, int cw) {
        // cw==w 表示装满了，i==n 表示物品都考察完了
        if (cw == w || i == n) {
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        if (mem[i][cw]) {
            // 重复状态
            return;
        }

        // 记录 (i, cw) 这个状态
        mem[i][cw] = true;

        // 选择不装第 i 个物品
        f2(i + 1, cw);

        if (cw + weight[i] <= w) {
            // 选择装第 i 个物品
            f2(i + 1, cw + weight[i]);
        }
    }

    /**
     * 解法三：动态规划解法
     * weight: 物品重量，n: 物品个数，w: 背包可承载重量
     */
    public int knapsack(int[] weight, int n, int w) {
        // 默认值 false
        boolean[][] states = new boolean[n][w + 1];
        // 第一行的数据要特殊处理，可以利用哨兵优化
        states[0][0] = true;
        states[0][weight[0]] = true;
        // 动态规划状态转移
        for (int i = 1; i < n; ++i) {
            // 不把第 i 个物品放入背包
            for (int j = 0; j <= w; ++j) {
                if (states[i - 1][j] == true) {
                    states[i][j] = states[i - 1][j];
                }
            }

            // 把第 i 个物品放入背包
            for (int j = 0; j <= w - weight[i]; ++j) {
                if (states[i - 1][j] == true) {
                    states[i][j + weight[i]] = true;
                }
            }
        } // end 状态转移设置

        // 输出结果
        for (int i = w; i >= 0; --i) {
            if (states[n - 1][i] == true) {
                return i;
            }
        }

        return 0;
    } // end 动态规划


    /**
     * 解法四：动态规划升级版
     */
    public int knapsack2(int[] items, int n, int w) {
        // 默认值 false
        boolean[] states = new boolean[w + 1];

        // 第一行的数据要特殊处理，可以利用哨兵优化
        states[0] = true;
        states[items[0]] = true;

        // 动态规划
        for (int i = 1; i < n; ++i) {
            for (int j = w - items[i]; j >= 0; --j) {
                // 把第 i 个物品放入背包
                if (states[j] == true) {
                    states[j + items[i]] = true;
                }
            }
        }

        // 输出结果
        for (int i = w; i >= 0; --i) {
            if (states[i] == true) {
                return i;
            }
        }

        return 0;
    }

    /**
     * 回溯法求最优值
     * 穷举所有状态获取最大值
     * <p>
     * 调用 f(0, 0, 0)
     */
    public void f(int i, int cw, int cv) {
        // cw==w 表示装满了，i==n 表示物品都考察完了
        if (cw == w || i == n) {
            if (cv > maxV) {
                maxV = cv;
            }
            return;
        }

        // 选择不装第 i 个物品
        f(i + 1, cw, cv);

        if (cw + weight[i] <= w) {
            // 选择装第 i 个物品
            f(i + 1, cw + weight[i], cv + value[i]);
        }
    }


    /**
     * 动态优化求最优解
     */
    public static int knapsack3(int[] weight, int[] value, int n, int w) {
        int[][] states = new int[n][w + 1];

        // 初始化 states
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < w + 1; ++j) {
                states[i][j] = -1;
            }
        }

        // 初始化第一行的值
        states[0][0] = 0;
        states[0][weight[0]] = value[0];

        // 动态规划，状态转移
        for (int i = 1; i < n; ++i) {
            // 不选择第 i 个物品
            for (int j = 0; j <= w; ++j) {
                if (states[i - 1][j] >= 0) {
                    states[i][j] = states[i - 1][j];
                }
            }

            // 选择第 i 个物品
            for (int j = 0; j <= w - weight[i]; ++j) {
                if (states[i - 1][j] >= 0) {
                    int v = states[i - 1][j] + value[i];
                    if (v > states[i][j + weight[i]]) {
                        states[i][j + weight[i]] = v;
                    }
                } // end one state handle
            }
        } // end 状态设置

        // 找出最大值
        int maxvalue = -1;
        for (int j = 0; j <= w; ++j) {
            if (states[n - 1][j] > maxvalue) {
                maxvalue = states[n - 1][j];
            }
        }

        return maxvalue;
    }

    /**
     * items 商品价格，n 商品个数, w 表示满减条件，比如 200
     */
    public static void double11advance(int[] items, int n, int w) {

        // 超过 3 倍就没有薅羊毛的价值了
        boolean[][] states = new boolean[n][3 * w + 1];

        // 第一行的数据要特殊处理
        states[0][0] = true;
        states[0][items[0]] = true;

        // 动态规划
        for (int i = 1; i < n; ++i) {
            // 不购买第 i 个商品
            for (int j = 0; j <= 3 * w; ++j) {
                if (states[i - 1][j] == true) {
                    states[i][j] = states[i - 1][j];
                }
            }

            // 购买第 i 个商品
            for (int j = 0; j <= 3 * w - items[i]; ++j) {
                if (states[i - 1][j] == true) {
                    states[i][j + items[i]] = true;
                }
            }
        }

        int j;
        // w=200, 满减条件
        for (j = w; j < 3 * w + 1; ++j) {
            if (states[n - 1][j] == true) {
                // 输出结果大于等于 w 的最小值
                break;
            }
        }

        if (j == 3 * w + 1) {
            // 没有可行解
            return;
        }

        // i 表示二维数组中的行，j 表示列
        for (int i = n - 1; i >= 1; --i) {
            if (j - items[i] >= 0 && states[i - 1][j - items[i]] == true) {
                // 购买这个商品
                System.out.print(items[i] + " ");
                j = j - items[i];
            }
            // else 没有购买这个商品，j 不变。
        }

        if (j != 0) {
            System.out.print(items[0]);
        }
    }

}
